import java.util.HashSet;
import java.util.PriorityQueue;

public class SmallestInfiniteSet {

    int count = 1;
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    HashSet<Integer> set = new HashSet<>();
    public SmallestInfiniteSet() {

    }

    public int popSmallest() {
        if (heap.size() == 0) {
            int temp = count;
            ++count;
            return temp;
        } else {
            Integer poll = heap.poll();
            set.remove(poll);
            return poll;
        }
    }

    public void addBack(int num) {
        if (num < count && !set.contains(num)) {
            set.add(num);
            heap.add(num);
        }
    }
}
